import java.util.*;


class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Partition {
    public ListNode partition( ListNode head,int x) {
        // write code here
        if(head == null){
            return null;
        }

        ListNode newHeadA = null;
        ListNode newHeadB = null;
        ListNode cur = head;
        ListNode curA = newHeadA;
        ListNode curB = newHeadB;

        while(cur != null){
            if(cur.val < x){
                if(newHeadA == null){
                    newHeadA = cur;
                    curA = cur;
                }else{
                    curA.next = cur;
                    curA = curA.next;
                }
            }else{
                if(newHeadB == null){
                    newHeadB = cur;
                    curB = cur;
                }else{
                    curB.next = cur;
                    curB = curB.next;
                }
            }
            cur = cur.next;
        }
        if(newHeadA == null){
            return newHeadB;
        }
        curA.next = newHeadB;
        if(newHeadB != null){
            curB.next = null;
        }
        return newHeadA;
    }
}